<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>列表转树</title>
</head>
<body>

	<script>
	/*
	使用对象存储数据, 典型的空间换时间

	时间复杂度为O(n)、空间复杂度为O(n)
	 */
	function listToTree(data) {
		// 使用对象重新存储数据, 空间换时间
		let map = {};
		// 存储最后结果
		let treeData = [];
		// 遍历原始数据 data，存到 map 中，id 为 key，值为数据
		for (let i = 0; i < data.length; i++) {
			map[data[i].id] = data[i];
		}

		// 遍历对象
		for (let i in map) {
			// 根据 parentId 找到的是父节点
			const parentId = map[i].parentId
			if (parentId) {
				if (!map[parentId].children) {
					map[parentId].children = [];
				}
			// 将子节点 放到 父节点的 children 中
				map[parentId].children.push(map[i]);
			} else {
			// parentId 找不到对应值，说明是根结点，直接插到根数组中
				treeData.push(map[i]);
			}
		}

		return treeData;
	}

	// 测试
	let list = [
	{ id: 1, title: "child1", parentId: 0 },
	{ id: 2, title: "child2", parentId: 0 },
	{ id: 6, title: "child2_1", parentId: 2 },
	{ id: 4, title: "child1_1", parentId: 1 },
	{ id: 5, title: "child1_2", parentId: 1 },
	{ id: 3, title: "child3", parentId: 0 },
	{ id: 7, title: "child3_1", parentId: 3 }
	];
	console.log(listToTree(list));
	</script>
</body>
</html>